/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30
␈↓ ↓H␈↓␈↓ ε(draft␈↓ H


␈↓ ↓H␈↓α␈↓ ∧&EXOTIC CONTINUOUS FUNCTIONALS


␈↓ ↓H␈↓α1. Some examples of exotic continuous functionals.

␈↓ ↓H␈↓␈↓ α_The␈αfixed␈αpoint␈αtheory␈αof␈αrecursive␈αfunctions␈αis␈αbased␈αon␈αcontinuous␈αfunctionals␈αsuch␈αas␈α␈↓	t␈↓
␈↓ ↓H␈↓defined by

␈↓ ↓H␈↓1)␈↓ α8  ␈↓↓␈↓	t␈↓↓[f](x) = ␈↓αif␈↓↓ p x ␈↓αthen␈↓↓ g x ␈↓αelse␈↓↓ m(x,f h x)␈↓.

␈↓ ↓H␈↓␈↓ α_The␈α∞theory␈α∞tells␈α∞us␈α∞that␈α∞each␈α∞continuous␈α∞monotonic␈α∞functional␈α∞has␈α∞a␈α∞fixed␈α∞point,␈α∞and␈α
we
␈↓ ↓H␈↓study␈α⊃the␈α⊃fixed␈α⊃points␈α∩of␈α⊃those␈α⊃functionals␈α⊃involved␈α⊃in␈α∩recursive␈α⊃definitions.␈α⊃ In␈α⊃the␈α∩case␈α⊃of
␈↓ ↓H␈↓recursive␈α
definitions␈α
␈↓↓␈↓	t␈↓↓[f](x)␈↓␈α
is␈α
a␈αform␈α
in␈α
which␈α
␈↓↓f␈↓␈α
appears␈αas␈α
a␈α
function␈α
symbol.␈α
 However,␈αthese
␈↓ ↓H␈↓are␈α⊂not␈α⊂all␈α⊂the␈α⊂continuous␈α⊂functions␈α⊂there␈α⊂are,␈α∂and␈α⊂it␈α⊂may␈α⊂be␈α⊂interesting␈α⊂to␈α⊂study␈α⊂some␈α∂other
␈↓ ↓H␈↓examples.  Consider functionals of the form

␈↓ ↓H␈↓2)␈↓ α8  ␈↓↓␈↓	t␈↓↓[f](x) = ␈↓αif␈↓↓ p x ␈↓αthen␈↓↓ g x ␈↓αelse␈↓↓ m f␈↓∧ -1␈↓↓ h x␈↓;

␈↓ ↓H␈↓that's␈αright,␈αwe␈αmean␈αthe␈αinverse␈αof␈αthe␈αfunction␈α␈↓↓f␈↓.␈α In␈αorder␈αto␈αmake␈αthe␈αfunctional␈αwell␈αdefined
␈↓ ↓H␈↓and␈α∩continuous,␈α∩we␈α∩make␈α∩the␈α∩following␈α∩stipulations:␈α∩ First,␈α∩the␈α∩variable␈α∩␈↓↓x␈↓␈α∩ranges␈α∩over␈α⊃non-
␈↓ ↓H␈↓negative integers and ␈↓↓f␈↓ is a partial function from integers to integers.  Second, we define ␈↓↓f␈↓∧ -1␈↓↓␈↓ by

␈↓ ↓H␈↓3)␈↓ α8  ␈↓↓f␈↓∧ -1␈↓↓(y) = ␈↓	m␈↓↓ x.(f(x) = y)␈↓,

␈↓ ↓H␈↓where

␈↓ ↓H␈↓4)␈↓ α8  ␈↓↓␈↓	m␈↓↓ x.p(x) ← least(0,p)␈↓,

␈↓ ↓H␈↓and ␈↓↓least(y,p)␈↓ is recursively defined by

␈↓ ↓H␈↓5)␈↓ α8  ␈↓↓least(y,p) ← ␈↓αif␈↓↓ p(y) ␈↓αthen␈↓↓ y ␈↓αelse␈↓↓ least(y+1,p)␈↓.

␈↓ ↓H␈↓Note␈α∩that␈α∩the␈α∩recursive␈α⊃definition␈α∩insures␈α∩that␈α∩␈↓↓f␈↓∧␈α⊃-1␈↓↓␈↓␈α∩is␈α∩continuous␈α∩in␈α⊃␈↓↓f,␈↓␈α∩and␈α∩that␈α∩␈↓	m␈↓x.␈↓↓p(x)␈↓␈α⊃is
␈↓ ↓H␈↓undefined␈α
if␈α
there␈α
is␈α
a␈α
value␈α
of␈α
␈↓↓x␈↓␈α
for␈α
which␈α
␈↓↓p(x)␈↓␈α
is␈α
undefined␈α
lower␈α
than␈α
a␈α
value␈α
for␈α
which␈α
␈↓↓p(x)␈↓␈α
is
␈↓ ↓H␈↓true.␈α Without␈αthis␈αproperty,␈α␈↓↓least(x,p)␈↓␈αwouldn't␈αbe␈αmonotonic␈αin␈α␈↓↓p␈↓,␈αand␈αthere␈αmightn't␈αbe␈αa␈αleast
␈↓ ↓H␈↓fixed point.

␈↓ ↓H␈↓␈↓ α_Consider specializing (2) to

␈↓ ↓H␈↓6)␈↓ α8  ␈↓↓␈↓	t␈↓↓1[f](x) = ␈↓αif␈↓↓ x = 0 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ 2 + f␈↓∧ -1␈↓↓(x - 1)␈↓.

␈↓ ↓H␈↓The fixed point ␈↓↓f1␈↓ of ␈↓	t␈↓1 may be computed by iterating ␈↓	t␈↓1 on ␈↓	W␈↓, getting

␈↓ ↓H␈↓7)␈↓ α8  ␈↓↓f1 x = ␈↓αif␈↓↓ x = 0 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x = 1 ␈↓αthen␈↓↓ 2 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x = 3 ␈↓αthen␈↓↓ 3 ␈↓αelse␈↓↓ ␈↓	w␈↓↓␈↓,

␈↓ ↓H␈↓which seems exotic if not pathological.

␈↓ ↓H␈↓␈↓ α_Wolf␈α⊂Polak␈α⊃points␈α⊂out␈α⊃that␈α⊂while␈α⊂␈↓	t␈↓1␈α⊃is␈α⊂exotic,␈α⊃its␈α⊂fixed␈α⊂point␈α⊃is␈α⊂an␈α⊃ordinary␈α⊂recursive
␈↓ ↓H␈↓function, since the recursive computation of ␈↓↓f␈↓∧ -1␈↓↓␈↓ can be spelled out.  Thus
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 91


␈↓ ↓H␈↓8)␈↓ α8  ␈↓↓f1 x ← ␈↓αif␈↓↓ x = 0 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ 2 + f2(0,x-1)␈↓,

␈↓ ↓H␈↓where

␈↓ ↓H␈↓9)␈↓ α8  ␈↓↓f2(y,x) ← ␈↓αif␈↓↓ f1(x) = y ␈↓αthen␈↓↓ x ␈↓αelse␈↓↓ f2(y+1,x)␈↓.

␈↓ ↓H␈↓␈↓ α_Here is another weird functional:

␈↓ ↓H␈↓10)␈↓ α8 ␈↓↓␈↓	t␈↓↓2[f](x) = ␈↓αif␈↓↓ p x ␈↓αthen␈↓↓ g x ␈↓αelse␈↓↓ ␈↓αif␈↓↓ f h1 x = ␈↓	w␈↓↓ ∧ f h2 x = ␈↓	w␈↓↓ ␈↓αthen␈↓↓ ␈↓	w␈↓↓ ␈↓αelse␈↓↓ f h3 x␈↓,

␈↓ ↓H␈↓where␈α␈↓↓p,␈↓␈α␈↓↓g,␈↓␈α␈↓↓h1,␈↓␈α␈↓↓h2␈↓␈αand␈α␈↓↓h3␈↓␈αare␈αall␈αassumed␈αtotal.␈α (Equality␈αhere␈αis␈αtaken␈αin␈αthe␈αstrong␈αsense␈αin
␈↓ ↓H␈↓which␈α
its␈α
value␈α
is␈α
always␈α
␈↓αtrue␈↓␈α
or␈α
␈↓αfalse␈↓␈α
and␈α
is␈α
never␈α
undefined).␈α
 Computing␈α
␈↓↓␈↓	t␈↓↓2[f](x)␈↓␈α
involves␈αa
␈↓ ↓H␈↓parallel␈αcomputation␈αof␈α␈↓↓f␈αh1␈α
x␈↓␈αand␈α␈↓↓f␈αh2␈αx␈↓;␈α
if␈αeither␈αsucceeds,␈αthe␈αother␈α
can␈αbe␈αstopped.␈α It␈αis␈α
easily
␈↓ ↓H␈↓seen␈αthat␈αthe␈αfunctional␈αis␈αcontinuous␈αand␈αhence␈αhas␈αa␈α
fixed␈αpoint␈α-␈αcall␈αit␈α␈↓↓f2.␈↓␈αIf␈αwe␈αcan␈αuse␈α
Lisp
␈↓ ↓H␈↓functions, we can write an ordinary recursive definition of ␈↓↓f2,␈↓ namely

␈↓ ↓H␈↓11)␈↓ α8 ␈↓↓f2 x ← ␈↓αif␈↓↓ p x ␈↓αthen␈↓↓ g x ␈↓αelse␈↓↓ (λy. f2 h3 x)(f2'(list(x),␈↓NIL␈↓↓))␈↓,

␈↓ ↓H␈↓with

␈↓ ↓H␈↓12)␈↓ α8␈α␈↓↓f2'(u,v)␈α←␈α␈↓αif␈↓↓␈α␈↓αn␈↓↓␈αu␈α␈↓αthen␈↓↓␈α(␈↓αn␈↓↓␈αv␈α∨␈αf2(v,␈↓NIL␈↓↓))␈α␈↓αelse␈↓↓␈αp␈αh1␈α␈↓αa␈↓↓␈αu␈α∨␈αp␈αh2␈α␈↓αa␈↓↓␈αu␈α∨␈αf2'(␈↓αd␈↓↓␈αu,␈αh1␈α␈↓αa␈↓↓␈αu␈α.
␈↓ ↓H␈↓↓(h2 ␈↓αa␈↓↓ u . v))␈↓.

␈↓ ↓H␈↓[Carolyn␈α
Talcott␈αpoints␈α
out␈α
that␈αthe␈α
above␈α
redefinition␈αis␈α
not␈α
correct␈αand␈α
has␈α
an␈αalternate␈α
breadth
␈↓ ↓H␈↓first search, but hadn't proved hers correct to her satisfaction at last discussion].

␈↓ ↓H␈↓If␈αwe␈αare␈αnot␈αallowed␈αto␈αuse␈αLisp␈αfunctions,␈αthen␈α␈↓↓f2␈↓␈αmay␈αbe␈αone␈αof␈αHewitt's␈αand␈αPaterson's␈α(197x)
␈↓ ↓H␈↓examples of functions that can be written with parallel programs but not with recursive programs.


␈↓ ↓H␈↓α2. When is a functional definable by a term?

␈↓ ↓H␈↓␈↓ α_In␈α
view␈α
of␈α
the␈α
above␈α
examples,␈α
we␈α
can␈α
try␈α
to␈α
characterize␈α
those␈α
continuous␈α
functional␈α
for
␈↓ ↓H␈↓which␈α␈↓↓␈↓	t␈↓↓[f](x)␈↓␈αcan␈αbe␈αwritten␈αas␈αa␈αterm␈αin␈α␈↓↓f␈↓␈αand␈α␈↓↓x␈↓␈αin␈αwhich␈α␈↓↓f␈↓␈αappears␈αas␈αa␈αfunction␈αsymbol␈αand␈α␈↓↓x␈↓
␈↓ ↓H␈↓as an individual variable.  Let's call them ␈↓↓term functionals␈↓.

␈↓ ↓H␈↓␈↓ α_If␈α
␈↓	t␈↓␈α
is␈α
a␈α
continuous␈α
functional,␈α
then␈α
the␈α
value␈α
of␈α
␈↓↓␈↓	t␈↓↓[f](x)␈↓␈α
depends␈α
on␈α
the␈α
value␈α
of␈α
␈↓↓f(y)␈↓␈αfor
␈↓ ↓H␈↓only␈αa␈αfinite␈αnumber␈αof␈α
␈↓↓y␈↓'s.␈α Namely,␈αthere␈αexist␈α␈↓↓y␈↓β1␈↓↓, ... ,y␈↓βk␈↓␈αsuch␈α
that␈α␈↓↓f(y)␈↓␈αcan␈αbe␈αchanged␈αfor␈α
any
␈↓ ↓H␈↓␈↓↓y␈↓␈α⊂different␈α⊂from␈α⊂the␈α⊂␈↓↓y␈↓βi␈↓'s␈α∂without␈α⊂changing␈α⊂the␈α⊂value␈α⊂of␈α∂␈↓↓␈↓	t␈↓↓[f](x)␈↓.␈α⊂ In␈α⊂general␈α⊂␈↓↓k␈↓␈α⊂depends␈α⊂on␈α∂the
␈↓ ↓H␈↓particular␈α␈↓↓f␈↓␈αand␈α␈↓↓x,␈↓␈αbut␈αwhen␈α␈↓	t␈↓␈αis␈αa␈αterm␈αfunctional,␈α␈↓↓k␈↓␈αis␈αbounded␈αby␈αthe␈αnumber␈αof␈αoccurrences
␈↓ ↓H␈↓of␈α␈↓↓f␈↓␈αin␈αthe␈αterm␈α␈↓↓␈↓	t␈↓↓[f](x)␈↓.␈α In␈αour␈αfirst␈αexotic␈αexample,␈αthe␈αnumber␈αof␈α␈↓↓f(y)␈↓␈αon␈αwhich␈α␈↓↓␈↓	t␈↓↓[f](x)␈↓␈αdepends
␈↓ ↓H␈↓is␈αunbounded,␈αbecause,␈αdepending␈αon␈α␈↓↓f,␈↓␈αany␈αfinite␈αnumber␈αof␈αof␈α␈↓↓f(x)␈↓'s␈αmay␈αhave␈αto␈αbe␈αexamined
␈↓ ↓H␈↓to␈α∞compute␈α∞␈↓↓f␈↓∧␈α
-1␈↓↓(y)␈↓.␈α∞ Tentatively,␈α∞we␈α∞shall␈α
call␈α∞a␈α∞functional␈α∞where␈α
such␈α∞a␈α∞bound␈α∞exists␈α
␈↓↓uniformly
␈↓ ↓H␈↓↓continuous␈↓,␈α
although␈α
we␈α∞have␈α
not␈α
yet␈α
been␈α∞able␈α
to␈α
establish␈α
any␈α∞properties␈α
in␈α
common␈α∞with␈α
the
␈↓ ↓H␈↓corresponding property in analysis.  Thus all ␈↓↓term functionals␈↓ are ␈↓↓uniformly continuous␈↓.

␈↓ ↓H␈↓␈↓ α_The␈α∩second␈α∪exotic␈α∩functional␈α∪is␈α∩uniformly␈α∩continuous␈α∪but␈α∩still␈α∪isn't␈α∩a␈α∪term␈α∩functional.
␈↓ ↓H␈↓Indeed every term functional has the another property that we may call ␈↓↓sequentiality␈↓:
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 92


␈↓ ↓H␈↓␈↓ α_Suppose␈α
that␈α
in␈α
evaluating␈α
␈↓↓␈↓	t␈↓↓[f](x)␈↓,␈α
we␈α
have␈α
already␈α
evaluated␈α␈↓↓f(x1),f(x2), ...,f(xk)␈↓.␈α
 There
␈↓ ↓H␈↓are␈α
two␈αpossibilities;␈α
 Either␈α
the␈αvalue␈α
of␈α␈↓↓␈↓	t␈↓↓[f](x)␈↓␈α
is␈α
already␈αdetermined␈α
by␈α
these␈αvalues␈α
or␈α␈↓↓f(y)␈↓␈α
must
␈↓ ↓H␈↓be␈α
computed␈α
for␈αadditional␈α
␈↓↓y␈↓'s.␈α
 We␈αcall␈α
␈↓	t␈↓␈α
␈↓↓sequential␈↓␈αif␈α
in␈α
the␈αlatter␈α
case␈α
there␈αis␈α
always␈α
at␈αleast
␈↓ ↓H␈↓one␈α⊃␈↓↓y␈↓␈α⊃such␈α⊃that␈α⊃␈↓↓␈↓	t␈↓↓[f](x)␈↓ = ␈↓	w␈↓␈α⊃unless␈α⊃␈↓↓f(y) ≠ ␈↓	w␈↓↓␈↓.␈α⊃ The␈α⊃function␈α⊃␈↓	t␈↓2␈α⊃of␈α⊃the␈α⊃previous␈α⊃section␈α⊃is␈α⊂not
␈↓ ↓H␈↓sequential.  If ␈↓	t␈↓ is sequential we can always write

␈↓ ↓H␈↓13)␈↓ α8␈α↔ ␈↓↓␈↓	t␈↓↓[f](x)␈α↔=␈α↔␈↓αif␈↓↓␈α↔p1␈α↔x␈α↔␈↓αthen␈↓↓␈α↔g1␈α↔x␈α↔␈↓αelse␈↓↓␈α↔{h1␈α↔x}[λx1.␈↓αif␈↓↓␈α↔p2(x,x1)␈α↔␈↓αthen␈↓↓␈α↔g2(x,x1)␈α↔␈↓αelse␈↓↓
␈↓ ↓H␈↓↓{h2(x,x1)}[λx2.␈↓αif␈↓↓ p3(x,x1,x2) ␈↓αthen␈↓↓ g3(x,x1,x2) ␈↓αelse␈↓↓ {h3(x,x1,x2}[λx3.␈↓αif␈↓↓ ... etc. ]]]␈↓.

␈↓ ↓H␈↓[We␈αuse␈αthe␈αnotation␈α␈↓↓{arg}fn␈↓␈αfor␈α␈↓↓fn(arg)␈↓␈αwhen␈αit␈αis␈αmore␈αconvenient␈αto␈αwrite␈αthe␈αargument␈αbefore
␈↓ ↓H␈↓the function].

␈↓ ↓H␈↓␈↓ α_Given␈αthat␈α␈↓	t␈↓␈αis␈αsequential,␈αthere␈αare␈αtwo␈αpossibilities.␈α If␈α␈↓	t␈↓␈αis␈αalso␈α␈↓↓uniformly␈αcontinuous␈↓␈αthe
␈↓ ↓H␈↓sequence␈α⊂of␈α⊂terms␈α⊂given␈α⊂in␈α⊂(13)␈α⊂will␈α⊂be␈α⊂finite␈α∂-␈α⊂otherwise␈α⊂not.␈α⊂ If␈α⊂the␈α⊂␈↓↓p␈↓'s,␈α⊂␈↓↓g␈↓'s␈α⊂and␈α⊂␈↓↓h␈↓'s␈α⊂are␈α∂all
␈↓ ↓H␈↓computable␈α∪in␈α∩some␈α∪collection␈α∪␈↓↓C␈↓␈α∩of␈α∪base␈α∪functions,␈α∩then␈α∪we␈α∩will␈α∪call␈α∪␈↓	t␈↓␈α∩computable␈α∪if␈α∪it␈α∩is
␈↓ ↓H␈↓sequential and bounded.  In that case its least fixed point will also be a computable function in ␈↓↓C␈↓.

␈↓ ↓H␈↓␈↓ α_While␈α∂sequentiality␈α∂requires␈α∂that␈α∂some␈α∂␈↓↓f(x)␈↓␈α⊂be␈α∂required␈α∂for␈α∂the␈α∂definedness␈α∂of␈α⊂␈↓↓␈↓	t␈↓↓[f](x)␈↓,␈α∂it
␈↓ ↓H␈↓doesn't require that ␈↓↓h(x)␈↓ be unique.  Thus if

␈↓ ↓H␈↓14)␈↓ α8  ␈↓↓␈↓	t␈↓↓[f](x) = f(m x) + f(n x)␈↓,

␈↓ ↓H␈↓we can take either ␈↓↓h1 x = m x␈↓ or ␈↓↓h1 x = n x␈↓.


␈↓ ↓H␈↓α3. Additional remarks.

␈↓ ↓H␈↓␈↓ α_1. Here are some more continuous ␈↓↓␈↓	t␈↓↓[f](x)␈↓:

␈↓ ↓H␈↓a. ␈↓↓f(x) ≠ ␈↓	w␈↓↓␈↓ for at least one ␈↓↓x.␈↓

␈↓ ↓H␈↓b. ␈↓↓f(x)+x ε A␈↓ for at least 20 odd values of ␈↓↓x.␈↓

␈↓ ↓H␈↓c. ␈↓↓R1(x,f h1 x) ∧ R2(x,f f h2 x)␈↓ for at least 20 ␈↓↓x.␈↓

␈↓ ↓H␈↓d. The functional

␈↓ ↓H␈↓␈↓ α_␈↓↓␈↓	t␈↓↓[f](x) = ␈↓αif␈↓↓ p1 x ␈↓αthen␈↓↓ g x ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ∃z.(f h1 z ≠ ␈↓	w␈↓↓) ␈↓αthen␈↓↓ f h2 z ␈↓αelse␈↓↓ ␈↓	w␈↓↓␈↓

␈↓ ↓H␈↓is␈αcontinuous.␈α It␈αcan't␈αbe␈αcomputed␈αfor␈αgeneral␈α␈↓↓f␈↓␈αexcept␈αby␈αparallel␈αevaluator,␈αbut␈αits␈αfixed␈αpoint
␈↓ ↓H␈↓can apparently be sequentially computed provided the domain of ␈↓↓x␈↓ can be effectively enumerated.

␈↓ ↓H␈↓␈↓ α_2.␈α
 Note␈αthat␈α
␈↓↓a␈↓␈α
thru␈α␈↓↓c␈↓␈α
above␈αare␈α
predicates,␈α
and␈αthe␈α
essential␈αpart␈α
of␈α
␈↓↓d␈↓␈αis␈α
also␈α
a␈αpredicate.
␈↓ ↓H␈↓Predicates␈αplay␈αa␈α
special␈αrole,␈αbecause␈α
it␈αis␈αeasier␈α
to␈αdefine␈αexotic␈α
continuous␈αpredicates␈αthan␈α
other
␈↓ ↓H␈↓functions.  The space whose elements are just T and ␈↓	w␈↓ seems to play a special role.

␈↓ ↓H␈↓John McCarthy
␈↓ ↓H␈↓Artificial Intelligence Laboratory
␈↓ ↓H␈↓Computer Science Department
␈↓ ↓H␈↓Stanford University
␈↓ ↓H␈↓␈↓ ε(draft␈↓ 93


␈↓ ↓H␈↓Stanford, California 94305

␈↓ ↓H␈↓ARPANET: MCCARTHY@SU-AI

␈↓ ↓H␈↓␈↓εThis draft of EXOTIC[W77,JMC] PUBbed at 22:29 on April 16, 1977.␈↓